package LeetCode;

import com.sun.org.apache.regexp.internal.RE;

/**
 * @author VX5
 * @Title: MJC
 * @ProjectName interview
 * @Description: TODO
 * @date ${DAT}17:01
 */
public class LeetCode494 {
    int count = 0;
    public int findTargetSumWays(int[] nums, int S) {
        if (nums == null || nums.length == 0){
            return 0;
        }
        dfs494(nums,0,S,0);
        return count;
    }

    public void dfs494(int[] nums,int index, int S,int sum){
        if (S == sum && index == nums.length){
            count++;
            return;
        }
        if (index == nums.length){
            return;
        }
        int temp = index + 1;
        dfs494(nums,temp,S,sum + nums[index]);
        dfs494(nums,temp,S,sum - nums[index]);
    }

    // 动态规划的解法
    public int findTargetSumWays2(int[] nums, int S) {
        int[][] dp = new int[nums.length][2001];
        dp[0][nums[0] + 1000] = 1;
        dp[0][-nums[0] + 1000] += 1;
        for (int i = 1; i < nums.length; i++){
            for (int sum = -1000; sum <= 1000; sum++){
                if (dp[i - 1][sum + 1000] > 0){
                    dp[i - 1][sum + nums[i] + 1000] += dp[i - 1][sum + 1000];
                    dp[i - 1][sum - nums[i] + 1000] += dp[i - 1][sum + 1000];
                }
            }
        }
        return S > 1000 ? 0:dp[nums.length - 1][S + 1000];
    }

    public static int findTargetSumWays3(int[] nums, int s) {
        int sum = 0;
        for (int i = 0; i < nums.length; i++) {
            sum += nums[i];
        }
        if (Math.abs(s) > sum){
            return 0;
        }
        int len = nums.length;
        int t = sum * 2 + 1;
        int[][] dp = new int[len][t];
        if (nums[0] == 0){
            dp[0][sum] = 2;//因为 之后要用到第一个数的时候+ - 情况都成立
        }else {
            dp[0][sum - nums[0]] = 1;
            dp[0][sum + nums[0]] = 1;
        }

        for (int i = 1; i < len; i++){
            for (int j = 0; j < t; j++){
                //设置一下边界
                int l = j - nums[i] <= 0 ? 0 : j - nums[i];
                int r = j + nums[i] >= t ? 0 : j + nums[i];
                dp[i][j] = dp[i - 1][l] + dp[i - 1][r];
            }
        }
        return dp[len - 1][sum + s];
//        // 绝对值范围超过了sum的绝对值范围则无法得到
//        if (Math.abs(s) > Math.abs(sum)) return 0;
//
//        int len = nums.length;
//        // - 0 +
//        int t = sum * 2 + 1;
//        int[][] dp = new int[len][t];
//        // 初始化
//        if (nums[0] == 0) {
//            dp[0][sum] = 2;
//        } else {
//            dp[0][sum + nums[0]] = 1;
//            dp[0][sum - nums[0]] = 1;
//        }
//
//        for (int i = 1; i < len; i++) {
//            for (int j = 0; j < t; j++) {
//                // 边界
//                int l = (j - nums[i]) >= 0 ? j - nums[i] : 0;
//                int r = (j + nums[i]) < t ? j + nums[i] : 0;
//                dp[i][j] = dp[i - 1][l] + dp[i - 1][r];
//            }
//        }
//        return dp[len - 1][sum + s];
    }


    public static void main(String[] args) {
        System.out.println(new LeetCode494().findTargetSumWays3(new int[]{1, 1, 1, 1, 1}, 3));
    }
}
